package com.ocean.everyday.d005_minimumsidewayjumps;

/**
 * https://leetcode.cn/problems/minimum-sideway-jumps/
 * <p>
 * 最少侧跳次数
 */
public class MinimumSidewayJumps2 {

    public static void main(String[] args) {
        MinimumSidewayJumps2 sidewayJumps = new MinimumSidewayJumps2();
        int[] nums = {0, 1, 2, 3, 0};
        int i = sidewayJumps.minSideJumps(nums);
        System.out.println(i);
        int[] nums2 = {0, 1, 1, 3, 3, 0};
        System.out.println(sidewayJumps.minSideJumps(nums2));
    }


    /**
     * obstacles = [0,1,2,3,0]
     *
     * @param obstacles
     * @return
     */
    public int minSideJumps(int[] obstacles) {
        final int INF = 0x3fffffff;
        int n = obstacles.length;
        int[] d = new int[3];
        d[0] = 1;
        d[1] = 0;
        d[2] = 1;
        for (int i = 1; i < n; i++) {
            // 找出当前点有没有障碍
            int item = obstacles[i];
            int min = INF;
            for (int j = 0; j < d.length; j++) {
                if (item - 1 == j) {
                    // 说明这条路有障碍
                    d[j] = INF;
                } else {
                    min = Math.min(min, d[j]);
                }
            }
            // 比较跳到该位置的
            for (int k = 0; k < d.length; k++) {
                if (obstacles[i] - 1 == k) {
                    continue; // 这个道路有障碍
                }
                // 没有障碍就比较直跳 跟侧跳的值
                d[k] = Math.min(d[k], min+1);
            }
        }
        return Math.min(Math.min(d[0],d[1]),d[2]);
    }

}
